package practice;

// 找最小栈！
// 两个栈：普通栈与最小栈
// 注意栈的初始化！

import java.util.Stack;

public class MinStack {
    // 两个栈声明
    Stack<Integer> stack; // 普通栈
    Stack<Integer> minStack; //最小栈

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    // 入栈：需要判断最小栈是否为空&&val与最小栈栈顶元素大小
    public void push(int val) {
        // 一定进入普通栈
        stack.push(val);
        // 判断最小栈是否为空
        if(minStack.empty()) {
            // 注意这里如果最小栈为空则直接装入元素！
            minStack.push(val);
        } else {
            int peekMin = minStack.peek(); // 获取最小栈栈顶元素（即：最小值）
            if(val <= peekMin) {
                minStack.push(val);
            }
        }
    }

    // 出栈：删除普通栈的栈顶:如果普通栈与最小栈栈顶元素相等，
    // 则最小栈栈顶元素也要出，不等就不用出，保证寻找最小值的正确性
    // 普通栈要判空：如果普通栈都为空，那么最小栈也一定为空
    public void pop() {
        // 普通栈判空
        // 只要普通栈不为空 最小栈一定不为空：因为二者最后都是一样的元素
        if(!stack.empty()) {
            // 普通栈一定出元素
            int popVal = stack.pop();
            //与最小栈栈顶元素进行比较
            int peekMin = minStack.peek();
            if(popVal == peekMin) {
                minStack.pop();
            }
        }

    }

    // 获取普通栈栈顶元素：直接弹出但不删除！:所以与最小栈无关
    // 判空
    public int top() {
        if(stack.empty()) {
            return -1;
        }
        // 来到这儿就是不空
        return stack.peek();
    }

    // 获取最小值（常数时间）--也就是最小栈栈顶元素
    // 但是注意：是获取但是不删除，所以用peek！
    public int getMin() {
        if(minStack.empty()) {
            return -1;
        }
       // return minStack.pop();
        return minStack.peek();
    }

    public static void main(String[] args) {
        System.out.println("测试：");

        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }
}
